#include "dichotomy.h"

dichotomy::dichotomy()
{

}

bool dichotomy::check(vector<int> &stones, int m)
{
    int n = stones.size();
    // 如果只走一步就大于 m，则 m 不可能
    for (int i=1; i < n; ++i)
        if (stones[i] - stones[i-1] > m)
            return false;
    vector<bool> vis(n, false);
    // 去的时候每一步都尽可能(<=m)向远跳
    for (int st=0; st < n-1;)
    {
        int ed = st+1;
        while (ed < n && stones[ed]-stones[st] <= m)
            ++ ed;
        --ed;
        vis[ed] = true;
        st = ed;
    }
    // 返回时，每一步的间隔都尽可能小，直接枚举所有未走的点之间的间隔即可
    vis[0] = false, vis[n-1] = false;
    for (int st=0; st < n-1;)
    {
        int ed = st+1;
        while (ed < n && vis[ed]==true)
            ++ ed;
        if (stones[ed] - stones[st] > m)
            return false;
        st = ed;
    }
    return true;
}

int dichotomy::maxJump(vector<int> &stones)
{
    // 二分
    int l = stones[1], r = 1e9 + 7;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (check(stones, mid))
            r = mid;
        else
            l = mid + 1;
    }
    return l;
};
